<?php

/**
 * 别称：黄金分割数列、兔子数列
 * 例子：1, 1, 2, 3, 5, 8, 13, 21...
 */
class 斐波那契数列
{
    /**
     * 暴力递归方式解决问题【时间复杂度为O(n^2)】
     */
    public function 暴力递归方式解决($num)
    {
        if ($num <= 0) {
            return 0;
        } elseif ($num <= 2) {
            return 1;
        } else {
            return $this->暴力递归方式解决($num - 1) + $this->暴力递归方式解决($num - 2);
        }
    }

    /**
     * 计算过的存储起来，减少重复计算【时间复杂度为O(n)】
     */
    public function 优化递归方式($num)
    {
        if ($num <= 0) {
            return 0;
        } elseif ($num <= 2) {
            return 1;
        } else {
            $numArr = [];
            return $this->计算斐波那契($numArr, $num);
        }
    }

    private function 计算斐波那契(&$numArr, $num)
    {
        if ($num == 1 || $num == 2) return 1;
        return $numArr[$num] ?? $this->计算斐波那契($numArr, $num - 1) + $this->计算斐波那契($numArr, $num - 2);
    }

    /**
     * 动态规划【时间复杂度为O(n)】
     */
    public function 动态规划解法($num)
    {
        if ($num < 2) return $num;
        $pre  = 0;
        $curr = 1;
        for ($i = 0; $i < $num - 1; $i++) { 
            $sum  = $pre + $curr;
            $pre  = $curr;
            $curr = $sum;
        }

        return $curr;
    }
}

$实例 = new 斐波那契数列();

$结果1 = $实例->暴力递归方式解决(7);
$结果2 = $实例->优化递归方式(7);
$结果3 = $实例->动态规划解法(7);

echo $结果1 . PHP_EOL;
echo $结果2 . PHP_EOL;
echo $结果3 . PHP_EOL;